package com.wuyou.mid;

import java.security.cert.CollectionCertStoreParameters;
import java.util.*;

/**
 * @Description 646. 最长数对链
 * @Author 无忧
 * @Date 2022/9/3 9:52
 */
public class FindLongestChain {

    public static void main(String[] args) {
        FindLongestChain findLongestChain = new FindLongestChain();
//        int[][] pairs = {{1, 2}, {2, 3}, {3, 4}};
//        int[][] pairs = {{1, 2}, {7, 8}, {4, 5}};
//        int[][] pairs = {{3, 4}, {2, 3}, {1, 2}};
//        int[][] pairs = {{-10, -8}, {8, 9}, {-5, 0}, {6, 10}, {-6, -4}, {1, 7}, {9, 10}, {-4, 7}};
//        int[][] pairs = {{-6, 9}, {1, 6}, {8, 10}, {-1, 4}, {-6, -2}, {-9, 8}, {-5, 3}, {0, 3}};
        int[][] pairs = {{7,9},{4,5},{7,9},{-7,-1},{0,10},{3,10},{3,6},{2,3}};
        System.out.println(findLongestChain.solution_1(pairs));
    }

    public int solution_2(int[][] pairs){
        Arrays.sort(pairs,(a,b)-> a[1]-b[1]);
        int res = 1,tmp = pairs[0][1];
        for(int i = 1;i < pairs.length;i++){
            if(pairs[i][0] > tmp){
                res++;
                tmp = pairs[i][1];
            }
        }
        return res;
    }
    public int solution_1(int[][] pairs) {
        if (pairs.length <= 1) {
            return 1;
        }
        int maxLength = 1;
        for (int i = 0; i < pairs.length; i++) {
            for (int j = i + 1; j < pairs.length; j++) {
                if (pairs[i][1] > pairs[j][1]) {
                    int[] temp = pairs[i];
                    pairs[i] = pairs[j];
                    pairs[j] = temp;
                }
            }
        }
        List<Integer> resList = new ArrayList<Integer>();
        int[] temp;
        for (int i = 0; i < pairs.length; i++) {
                temp = pairs[i];
            for (int j = i + 1; j < pairs.length; j++) {
                if (temp[1] < pairs[j][0]) {
                    maxLength++;
                    temp = pairs[j];

                }
            }
            resList.add(maxLength);
            maxLength = 1;
        }
        return Collections.max(resList);
    }
}
